package class04;

/**
 * 题目：交错字符串
 * 
 * 描述：
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。
 * 两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 提示：a + b 意味着字符串 a 和 b 连接。
 * 
 * 示例：
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 * 输出：true
 * 
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 * 输出：false
 * 
 * 解题思路：
 * 使用动态规划方法解决此问题。
 * 定义dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前(i+j)个字符。
 * 状态转移方程：
 * dp[i][j] = (str1[i-1] == str3[i+j-1] && dp[i-1][j]) || 
 *            (str2[j-1] == str3[i+j-1] && dp[i][j-1])
 */
// 本题测试链接 : https://leetcode.com/problems/interleaving-string/
public class Code07_InterleavingString {

	/**
	 * 判断s3是否由s1和s2交错组成
	 * 
	 * @param s1 第一个字符串
	 * @param s2 第二个字符串
	 * @param s3 待判断的交错字符串
	 * @return 如果s3由s1和s2交错组成返回true，否则返回false
	 */
	public static boolean isInterleave(String s1, String s2, String s3) {
		// 检查输入参数是否为空
		if (s1 == null || s2 == null || s3 == null) {
			return false;
		}
		
		// 将字符串转换为字符数组便于操作
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		char[] str3 = s3.toCharArray();
		
		// 如果s3的长度不等于s1和s2长度之和，则不可能是交错组成
		if (str3.length != str1.length + str2.length) {
			return false;
		}
		
		// 创建DP表，dp[i][j]表示s1前i个字符和s2前j个字符能否交错组成s3前(i+j)个字符
		boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
		
		// 初始化基本情况：两个空字符串可以交错组成一个空字符串
		dp[0][0] = true;
		
		// 填充第一列：只有s1字符参与的情况
		for (int i = 1; i <= str1.length; i++) {
			// 如果当前字符不匹配，则后续都不可能匹配
			if (str1[i - 1] != str3[i - 1]) {
				break;
			}
			dp[i][0] = true;
		}
		
		// 填充第一行：只有s2字符参与的情况
		for (int j = 1; j <= str2.length; j++) {
			// 如果当前字符不匹配，则后续都不可能匹配
			if (str2[j - 1] != str3[j - 1]) {
				break;
			}
			dp[0][j] = true;
		}
		
		// 填充DP表的其余位置
		for (int i = 1; i <= str1.length; i++) {
			for (int j = 1; j <= str2.length; j++) {
				// 状态转移方程：
				// 如果s1的第i个字符与s3的第(i+j)个字符匹配，并且前(i-1,j)可以交错组成s3的前(i+j-1)个字符
				// 或者s2的第j个字符与s3的第(i+j)个字符匹配，并且前(i,j-1)可以交错组成s3的前(i+j-1)个字符
				if (
						(str1[i - 1] == str3[i + j - 1] && dp[i - 1][j])




						||



						(str2[j - 1] == str3[i + j - 1] && dp[i][j - 1])


						) {
					dp[i][j] = true;
				}
			}
		}
		
		// 返回最终结果
		return dp[str1.length][str2.length];
	}

}
